package com.wfs.suanfa.leet;

import javafx.util.Pair;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 贪心算法
 * https://blog.csdn.net/baichendada/article/details/122980730
 * @author wfs
 * @date 2022-02-24 16:46
 */
public class TanXinTest {
    public static void main(String[] args) {
        int[] arr=new int[]{1,4,5,6,1,9,6,8};
        int[] arr1=new int[]{0,0,0};
        int[] maxProfitOneArr=new int[]{7,6,4,3,1};
        System.out.println(maxProfitOne(maxProfitOneArr));
       // System.out.println(canJump(arr));
        //System.out.println(greedStrategy(arr, arr1));
        Pair<Integer,Integer>[] pairs=new Pair[5];
        pairs[0]=new Pair<>(1,2);
        pairs[1]=new Pair<>(2,2);
        pairs[2]=new Pair<>(1,2);
        pairs[3]=new Pair<>(6,10);
        pairs[4]=new Pair<>(3,6);
        //System.out.println(greedyActivitySelector(pairs));
        //System.out.println(maxEvents(pairs));
        //System.out.println(eraseOverlapIntervals(pairs));

    }
    /**
     * 买卖最佳 同一天可以买入加卖出
     */
    static int maxProfit(int[] arr){
        int max=0;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i-1]<arr[i]){
                max+=arr[i]-arr[i-1];
            }
        }
        return max;
    }
    /**
     * 买卖最佳 只有一次买入卖出
     */
    static int maxProfitOne(int[] arr){
        int max=0;
        int tempMax=0;
        int min=128;
        for (int i = 0; i < arr.length;i++) {
            min=Math.min(arr[i],min);
            tempMax=Math.max(arr[i],min);
            if ((tempMax-min)>max){
                max=tempMax-max;
            }
        }
        return max;
    }
    /**
     * 可跳转查询
     */
    static  boolean canJump(int[] arr){
        int max=0;
        int len=arr.length;
        for (int i = 0; i < arr.length; i++) {
            if (max<i){
                return false;
            }
            max=Math.max(max,i+arr[i]);
        }
        return true;
    }
    /**
     * 多机调度问题， n个任务执行分别是t1,t2,t3....,有m台相同机器，获得最短任务执行时间
     * @param works 任务
     * @param machines 机器
     */
    static int greedStrategy(int[] works,int[] machines){
        //排序操作 从小到大
        Arrays.sort(works);
        int workNum = works.length;
        int machineNum = machines.length;
        // 如果 n <= m ，返回任务中时间最长的一项任务
        if (workNum <= machineNum)
            return works[0];
        // 选择机器执行每一个任务 任务需要从最大执行任务时间计算
        for (int i = workNum-1; i >= 0;i--)
        {
            int flag = 0;
            // 选择现在执行任务花费时间最少的机器
            for (int j = 1; j < machineNum; ++j)
            {
                if (machines[j] < machines[flag])
                    flag = j;
            }
            // 执行本次任务
            machines[flag] += works[i];
        }
        // 选出用时最长的机器
        int max = 0;
        for(int e : machines)
        {
            if (e > max)
                max = e;
        }
        // 返回时间
        return max;
    }
    /**
     *有n个需要在同一天使用同一个教室的活动a1, a2, …, an，教室同一时刻只能由一个活动使用。
     * 每个活动a[i]都有一个开始时间s[i]和结束时间f[i]。一旦被选择后，活动a[i]就占据半开时间区间[s[i],f[i])。
     * 如果[s[i],f[i])和[s[j],f[j])互不重叠，a[i]和a[j]两个活动就可以被安排在这一天。
     * 求使得尽量多的活动能不冲突的举行的最大数量
     */
    static int greedyActivitySelector(Pair<Integer,Integer>[] arr){
        int max=0;
        //按照结束时间进行排序
        List<Pair<Integer, Integer>> collect = Arrays.stream(arr).sorted(new Comparator<Pair<Integer, Integer>>() {
            @Override
            public int compare(Pair<Integer, Integer> o1, Pair<Integer, Integer> o2) {
                return o1.getValue() - o2.getValue();
            }
        }).collect(Collectors.toList());
        //结束时间
        int end=1;
        for (Pair<Integer, Integer> e : collect) {
            if (e.getKey()>=end){
                end=e.getValue();
                max++;
            }

        }
        return max;
    }

    /**
     * 最多可以参加会议数
     * 复杂度有点高，需要优化
     */
    static int maxEvents(Pair<Integer,Integer>[] arr){
        int max=0;
        //按照结束时间进行排序,结束时间相同按照开始时间排序
        List<Pair<Integer, Integer>> collect = Arrays.stream(arr).sorted(new Comparator<Pair<Integer, Integer>>() {
            @Override
            public int compare(Pair<Integer, Integer> o1, Pair<Integer, Integer> o2) {
                if (o1.getValue()!=o2.getValue()){
                   return o1.getValue() - o2.getValue();
                }else {
                    return o1.getKey() - o2.getKey();
                }
            }
        }).collect(Collectors.toList());
        Map<Integer,Integer> map=new HashMap<>();
        for (Pair<Integer, Integer> e : collect) {
            for (Integer i = e.getKey(); i < e.getValue(); i++) {
                if (!map.containsKey(i)){
                    max++;
                    break;
                }
            }
        }
        return max;
    }
    static int maxEventsTwo(Pair<Integer,Integer>[] arr){
        int max=0;
        return max;
    }
    /**
     * 无重叠区间
     */
    static int eraseOverlapIntervals(Pair<Integer,Integer>[] arr){
        //按照结束时间进行排序,结束时间相同按照开始时间排序
        List<Pair<Integer, Integer>> collect = Arrays.stream(arr).sorted(new Comparator<Pair<Integer, Integer>>() {
            @Override
            public int compare(Pair<Integer, Integer> o1, Pair<Integer, Integer> o2) {
                if (o1.getValue()!=o2.getValue()){
                    return o1.getValue() - o2.getValue();
                }else {
                    return o1.getKey() - o2.getKey();
                }
            }
        }).collect(Collectors.toList());
        //记录最大重叠数
        int max=0;
        int end=collect.get(0).getValue();
        for (int i = 1; i < collect.size(); i++) {
            //结束时间<开始时间说明未重叠
            if (end<=collect.get(i).getKey()){
                //
                end=collect.get(i).getValue();
                max++;
            }
        }
        return arr.length-max;
    }


}
